<head>
    <meta charset="UTF-8">
<title>算法提高 双十一抢购</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】<br />
一年一度的双十一又来了，某网购网站又开始了半价销售的活动。<br />
小G打算在今年的双十一里尽情地购物，以享受购买的极度快感，她已经列好了她想买的物品的列表。<br />
当然小G并不是出身富贵家庭，所以她网银里的钱只是一个有限的整数S（单位：元）。<br />
这次抢购她打算遵循这三个原则选择每一个物品：<br />
1.先买能&ldquo;赚&rdquo;最多的；<br />
2.在&ldquo;赚&rdquo;一样多的情况下，先买最便宜的（这样买的东西就可能更多了）；<br />
3.在前两条里都判断不了购买顺序的话，先购买在列表里靠前的。<br />
（由于网站里还是有一部分商品并没有打五折，所以2的情况（&ldquo;赚&rdquo;的钱数为0）是完全可能发生的）<br />
现在，在双十一的这一天，你要帮小G编写一个程序，来看看她应该去买她列表里的哪些物品。（总价格不要超过S哦）<br />
要是帮她写好这个程序的话，或许你能在光棍节这一天里赢得她的芳心哦~<br />
【输入格式】<br />
输入共N+1行。<br />
第一行包含两个整数S和N，S表示小G的可用金额，N表示她看上的物品个数。<br />
接下来N行，对应每一个物品，每行有两个整数a和b，a是物品的原价（单位：元），b为0或1，若b为0，则此物品不半价，若b为1，则此物品半价销售。<br />
【输出格式】<br />
输出共一行，为小G要买的物品序号（从1开始），用空格隔开，注意按序号从小到大输出。<br />
若小G一件都买不了，则输出0.<br />
【样例输入1】<br />
10 3<br />
5 0<br />
4 0<br />
10 1<br />
【样例输出1】<br />
2 3<br />
【样例输入2】<br />
10 3<br />
11 0<br />
21 1<br />
100 1<br />
【样例输出2】<br />
0<br />
【数据规模和约定】<br />
0&lt;S&lt;=10000,0&lt;N&lt;=1000,每一个a和b满足0&lt;a&lt;=1000且b=0或1。</p>